home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / comm / bbs / cit_src_7H21.lha / slist.c < prev    next >
C/C++ Source or Header  |  1997-08-14  |  12KB  |  400 lines
  1. /*
  2. * SList.C
  3. *
  4. * Copyright (c) 1989 by Hue, Jr.  All Rights Reserved.
  5. *
  6. * This is a generic, messy list handler.
  7. * VARIANT: this one automatically sorts the list where allowed.
  8. */
  9. #include "ctdl.h"
  10. #include "stdio.h"
  11. #include "stdlib.h"
  12. #include "string.h"
  13. #include "slist.h"
  14. #define TRUE    1
  15. #define FALSE   0
  16. extern CONFIG    cfg;
  17. void  Do_Stack_Check(void);
  18. /*
  19. * History
  20. *
  21. * 89Jan22 HAW  Variant for keeping sorted lists.
  22. * 89Jan01 HAW  Completed initial version.
  23. */
  24. /************************************************************************/
  25. /*                              Contents                                */
  26. /*                                                                      */
  27. /*                      Generic Functions                               */
  28. /*                                                                      */
  29. /*      AddData()               Add an element of data to a list        */
  30. /*      KillData()              remove an element of data from a list   */
  31. /*      KillList()              Destroys a list                         */
  32. /*      MakeList()              Construct a disk-based list in memory   */
  33. /*      RunList()               run a function on a list                */
  34. /*      SearchList()            search a list for a given data element  */
  35. /*                                                                      */
  36. /************************************************************************/
  37. /*
  38. * Usage
  39. *
  40. * This module contains a generic list handler.
  41. *
  42. *  o Initialization - before a list can contain things, it must be
  43. *  initialized.  Initialization consists of declaring some variable to
  44. *  be of type SListBase (this variable will be what you use to access
  45. *  the list), and ensuring it is initialized correctly before use.
  46. *  Initialization may be accomplished either via initializers or
  47. *  manually.  In any case, this is what each field must be initialized
  48. *  to:
  49. *  - start -- initialize to NULL in ALL cases.
  50. *  - CheckIt -- initialize to point to a function capable of comparing
  51. *        two data structs for equality on some arbitrary, meaningful
  52. *        quality (specifically NOT the value of the void pointer itself!).
  53. *        If equal, it should return a pointer to some value which will be
  54. *        useful in that context, otherwise NULL.
  55. *  - cmp -- initialize to point to a function which accepts to two void *
  56. *        variables, i.e., must like qsort: cmp(void *s1, void *s2).  This
  57. *        function should return < 0 if s1 < s2, > 0 if s1 > s2, == 0 if the
  58. *        two variables are 'equal'.  If this field is NULL, then the list
  59. *        will not be sorted.
  60. *  - FreeFunc -- some function capable of freeing an unneeded data
  61. *        instance from the list.
  62. *  - EatLine -- some function capable of digesting a line of data from
  63. *        a text file and producing a pointer to a new data instance with
  64. *        the results of the digestion entombed within for later use.
  65. *
  66. *  o Briefly, here are the currently supported services for list
  67. *  handling.
  68. *  - MakeList will construct a list from the given text file, using the
  69. *        EatLine function outlined above.
  70. *  - AddData will add a single data element to the list.  Data element
  71. *        in toto must be provided by the user.  Optionally will kill
  72. *        duplicates (detected using CheckIt function) from list, optionally
  73. *        will "write" list after addition (very blind - check code).
  74. *  - KillData will kill the specified data element from the list, using
  75. *        CheckIt to find them.  All instances will be deleted.
  76. *  - KillList will kill the list.  (Not implemented yet.)
  77. *  - SearchList will search the list for the given data element, using
  78. *        CheckIt to detect it.  If found, a void * will be returned to the
  79. *        caller, for its own interpretation.  The pointer returned will be
  80. *        the same as that returned by the CheckIt function.
  81. *  - RunList will apply the specified function to all members of the
  82. *        list.
  83. *
  84. *  This module needs the function void *GetDynamic(int size) to be
  85. *  defined as a function which returns size bytes of dynamic memory.
  86. */
  87.  
  88. #ifdef OLD_STYLE
  89. void *GetDynamic(int size);
  90. #else
  91. void *(*slistmalloc)(unsigned size) = malloc;
  92. void  (*slistfree)(void *)     = free;
  93. #endif
  94.  
  95.  
  96.  
  97. /*
  98. * MakeList(SListBase *base, char *fn, FILE *fd)
  99. *
  100. * This function will construct a list by reading from a text file and asking
  101. * a specified function to process the text.  If strlen(fn) == 0, it will use
  102. * File fd passed in, otherwise it will try to open fn in text mode.
  103. */
  104. char MakeList(base, fn, fd)
  105. SListBase *base;
  106. char         *fn;
  107. FILE         *fd;
  108.   {
  109.   char        line[160];
  110.   void        *temp;
  111.   Do_Stack_Check();
  112.   if (strlen(fn))
  113.     {
  114.     if (cfg.BoolFlags.debug) splitF(NULL,"Open file:%s\n",fn);
  115.     if ((fd = fopen(fn, "r")) == NULL)return FALSE;
  116.  
  117.     }
  118.   while (GetAString(line, 80, fd) != NULL)
  119.     {
  120.     if (cfg.BoolFlags.debug) splitF(NULL,"eat line:%s\n",line);
  121.     if ((temp = (*base->EatLine)(line)) != NULL)
  122.       {
  123.       AddData(base, temp, NULL, FALSE);
  124.  
  125.       }
  126.  
  127.     }
  128.   if (strlen(fn)) fclose(fd);
  129.   if (cfg.BoolFlags.debug) splitF(NULL,"Closed:%s\n",fn);
  130.   return TRUE;
  131.  
  132.   }
  133. /*
  134. * char *GetAString(char *line, int size, FILE *fd)
  135. *
  136. * Gets a string from the file, chops off the EOL.  If EOF, returns NULL.
  137. */
  138. char *GetAString(char *line, int size, FILE *fd)
  139.   {
  140.   char *s;
  141.   Do_Stack_Check();
  142.   if (fgets(line, size, fd) != NULL)
  143.     {
  144.     if ((s = strchr(line, '\n')) != NULL)    *s = 0;
  145.     if ((s = strchr(line, '\r')) != NULL)    *s = 0;
  146.     return line;
  147.  
  148.     }
  149.   return NULL;
  150.  
  151.   }
  152. /************************************************************************/
  153. /*          AddData() Add an element of data to a list                  */
  154. /************************************************************************/
  155. void AddData(base, data, writeit, killdups)
  156. SListBase *base;
  157. void                *data;
  158. int                 killdups;
  159. void                (*writeit)(void *data);
  160.   {
  161.   SListData *rover, *rover2, *trail = NULL;
  162.   Do_Stack_Check();
  163.   if (killdups)
  164.   KillData(base, data);
  165.   rover = (SListData *) GetDynamic(sizeof *rover);
  166.   if (base->start == NULL)
  167.     {
  168.     base->start = rover;
  169.     rover->next = NULL;
  170.  
  171.     }
  172.   else
  173.     {
  174.     for (rover2 = base->start;
  175.     rover2 != NULL &&
  176.     (base->cmp == NULL ||
  177.     (*base->cmp)(rover2->data, data) < 0) ;
  178.     rover2 = rover2->next)
  179.     trail = rover2;
  180.     if (trail == NULL)
  181.       {
  182.       rover->next = base->start;
  183.       base->start = rover;
  184.  
  185.       }
  186.     else
  187.       {
  188.       rover->next = trail->next;
  189.       trail->next = rover;
  190.  
  191.       }
  192.  
  193.     }
  194.   rover->data = data;
  195.   if (writeit != NULL)
  196.   RunList(base, writeit);
  197.  
  198.   }
  199.  
  200. /************************************************************************/
  201. /*    AltKillData() remove an element of data from a list       */
  202. /************************************************************************/
  203. void AltKillData(base, check, data)
  204. SListBase *base;
  205. void    *data;
  206. void    *(*check)();
  207. {
  208.     SListData *rover, *trail, *moo;
  209.  
  210.     trail = base->start;
  211.     rover = base->start;
  212.  
  213.     while (rover != NULL) {
  214.         if ((*check)(rover->data, data) != NULL) {
  215.             moo = rover->next;
  216.             (*base->FreeFunc)(rover->data);
  217.             (*slistfree)(rover);
  218.             if (trail == rover)
  219.                 rover = trail = base->start = moo;
  220.             else
  221.                 trail->next = rover = moo;
  222.         }
  223.         else {
  224.             trail = rover;
  225.             rover = rover->next;
  226.         }
  227.     }
  228. }
  229.  
  230.  
  231. /************************************************************************/
  232. /*          KillData() remove an element of data from a list            */
  233. /************************************************************************/
  234. void KillData(base, data)
  235. SListBase *base;
  236. void        *data;
  237.   {
  238.   Do_Stack_Check();
  239.   if (base->CheckIt == NULL) return;
  240.  
  241.   AltKillData(base, base->CheckIt, data);
  242.  
  243.   }
  244. /************************************************************************/
  245. /*          KillList() Destroys a list                                  */
  246. /************************************************************************/
  247. void KillList(base)
  248. SListBase *base;
  249.   {
  250.   SListData *rover, *b;
  251.   Do_Stack_Check();
  252.   for (b = base->start; b != NULL; )
  253.     {
  254.     rover = b->next;
  255.     (*base->FreeFunc)(b->data);
  256.     free(b);
  257.     b = rover;
  258.  
  259.     }
  260.   base->start = NULL;
  261.  
  262.   }
  263.  
  264. /*
  265.  *    MaybeKillList() Destroys a list
  266.  */
  267. void MaybeKillList(base, func)
  268. SListBase *base;
  269. int (*func)();
  270. {
  271.         SListData *rover, *b, *trail;
  272.  
  273.         for (b = base->start, trail = NULL; b != NULL; ) {
  274.                 rover = b->next;
  275.                 if ((*func)(b->data)) {
  276.                         (*base->FreeFunc)(b->data);
  277.                         if (b == base->start) base->start = rover;
  278.                         if (trail != NULL) trail->next = rover;
  279.             (*slistfree)(b);
  280.                 }
  281.                 else trail = b;
  282.                 b = rover;
  283.         }
  284. }
  285.  
  286.  
  287. /************************************************************************/
  288. /*          SearchList() search a list for a given data element         */
  289. /************************************************************************/
  290. void *SearchList(base, data)
  291. SListBase *base;
  292. void        *data;
  293.   {
  294.   SListData *rover;
  295.   void         *temp;
  296.   Do_Stack_Check();
  297.   for (rover = base->start; rover != NULL; rover = rover->next)
  298.   if ((temp = (*base->CheckIt)(rover->data, data)) != NULL)
  299.   return temp;
  300.   return NULL;
  301.  
  302.   }
  303.  
  304.  
  305. void *AltSearchList(SListBase *base, void *(*doit)(), void *data)
  306. {
  307.     SListData *rover;
  308.     void     *temp;
  309.  
  310.     for (rover = base->start; rover != NULL; rover = rover->next)
  311.         if ((temp = (*doit)(rover->data, data)) != NULL)
  312.             return temp;
  313.  
  314.     return NULL;
  315. }
  316.  
  317.  
  318. /************************************************************************/
  319. /*          RunList() run a function on a list                          */
  320. /************************************************************************/
  321. int RunList(base, doit)
  322. SListBase *base;
  323. void        (*doit)(void *data);
  324.   {
  325.   SListData *rover;
  326.   int       count = 0;
  327.   Do_Stack_Check();
  328.   for (rover = base->start; rover != NULL; rover = rover->next, count++)
  329.   (*doit)(rover->data);
  330.   return count;
  331.  
  332.   }
  333.  
  334.  
  335. /*
  336.  * RunListA()
  337.  *
  338.  * run a function on a list
  339.  */
  340. int RunListA(base, doit, arg)
  341. SListBase *base;
  342. void    (*doit)(void *data, void *rg), *arg;
  343. {
  344.     SListData *rover;
  345.     int       count = 0;
  346.  
  347.     for (rover = base->start; rover != NULL; rover = rover->next, count++)
  348.         (*doit)(rover->data, arg);
  349.  
  350.     return count;
  351. }
  352.  
  353.  
  354.  
  355. /*
  356. * void FrontToEnd(SListBase *base)
  357. *
  358. * This function takes the first element of the list, if it exists, and makes
  359. * it the last element of the list.  This is useful for lists whose sort order
  360. * changes due to outside forces.
  361. */
  362. void FrontToEnd(base)
  363. SListBase *base;
  364.   {
  365.   SListData *r1, *r2;
  366.   Do_Stack_Check();
  367.   if (base->start != NULL && base->start->next != NULL)
  368.     {
  369.     r1 = base->start;
  370.     base->start = r1->next;
  371.     for (r2 = r1; r2->next != NULL; r2 = r2->next)
  372.     ;
  373.     r2->next = r1;
  374.     r1->next = NULL;
  375.  
  376.     }
  377.  
  378.   }
  379. void NoFree(void *d)
  380.   {
  381.   Do_Stack_Check();
  382.  
  383.   }
  384. /*
  385. * void *GetLast(SListBase *base)
  386. *
  387. * This function finds the last element in the list and returns it.  It
  388. * returns NULL if the list is empty.
  389. */
  390. void *GetLast(SListBase *base)
  391.   {
  392.   SListData *rover;
  393.   Do_Stack_Check();
  394.   if (base->start == NULL) return NULL;
  395.   for (rover = base->start; rover->next != NULL; rover = rover->next)
  396.   ;
  397.   return rover->data;
  398.  
  399.   }
  400.